/**
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 



以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

 



图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

 

示例:

输入: [2,1,5,6,2,3]
输出: 10å

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> temp;
        vector<int> leftM(heights.size()),rightM(heights.size());
        for(int i=0;i<heights.size();i++){
            while(!temp.empty()&&heights[temp.top()]>=heights[i]){
                temp.pop();
            }
            if(temp.empty()){
                leftM[i]=(-1);
            }else{
                leftM[i]=(temp.top());
            }
            temp.push(i);
        }
        while(!temp.empty()){
            temp.pop();
        }
        for(int i=heights.size()-1;i>=0;i--){
            while(!temp.empty()&&heights[temp.top()]>=heights[i]){
                temp.pop();
            }
            if(temp.empty()){
                rightM[i]=(heights.size());
            }else{
                rightM[i]=(temp.top());
            }
            temp.push(i);
        }
        int res=0;
        for(int i=0;i<heights.size();i++){
            res=max(res,heights[i]*(rightM[i]-leftM[i]-1));
        }
        return res;
    }
};